package com.atguigu.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰表达式实现计算器的计算(计算的表达式要满足逆波兰表达式)
 *
 * 中缀表达式转成后缀表达式
 *
 * @author WangJX
 * @version 1.0
 * @date 2019/10/15 22:40
 */
public class PolandNotation {
    public static void main(String[] args) {
        /*
        //原计算公式是：(3 + 4) * 5 - 6 => 逆波兰表示式后：3 4 + 5 x 6 -
        //4 5 x 8 - 6 + 8 2 / +
        String suffixExpression = "4 5 x 8 - 60 + 8 2 / +";

        List<String> string = getListString(suffixExpression);

        int calculater = calculater(string);
        System.out.println("运算的结果是：(" + suffixExpression + ") = " + calculater);
        */

//        List<String> list = toInfixExpressionList("1+((2+3)x4)-5");
        List<String> list = toInfixExpressionList("(30+4)x5-6");
        System.out.println("中缀表达式=" + list);
        System.out.println(pareseSuffixExpressionList(list));
        System.out.println(calculater(pareseSuffixExpressionList(list)));
    }

    /**
     * 解析逆波兰表达式存储在List中
     *
     * @param suffixExpression
     * @return
     */
    public static List<String> getListString(String suffixExpression) {
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String suf : split) {
            list.add(suf);
        }
        return list;
    }

    /**
     * 计算逆波兰表达式
     *
     * @param list
     * @return
     */
    public static int calculater(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String val : list) {
            //用正则表达式判断是否是数字
            if (val.matches("\\d+")) {
                //放入栈中
                stack.push(val);
            } else {
                //如果是运算符
                int result = 0;
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                if (val.equalsIgnoreCase("+")) {
                    result = num1 + num2;
                } else if (val.equalsIgnoreCase("-")) {
                    result = num1 - num2;
                } else if (val.equalsIgnoreCase("x")) {
                    result = num1 * num2;
                } else if (val.equalsIgnoreCase("/")) {
                    result = num1 / num2;
                } else {
                    throw new RuntimeException("输入的运算符有误！");
                }
                stack.push("" + result);
            }
        }
        return Integer.parseInt(stack.pop());
    }


    //将一个中缀表达式转化成对应的list
    // 1+((2+3)x4)-5 => 1 2 3 + 4 x + 5 -
    // (30+4)x5-6  =>  30 4 + 5 x 6   =    164
    public static List<String> toInfixExpressionList(String s) {
        List<String> list = new ArrayList<>();

        int i = 0;
        String v;
        char c;

        while (i < s.length()) {
            //判断是否为非数字
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                list.add("" + c);
                i++;
            } else {
                v = "";
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    v += c;
                    i++;
                }
                list.add(v);
            }
        }

        return list;
    }


    /**
     * 将一个中缀表达式转化成一个后缀表达式
     *
     * @param strings   一个中缀表达式
     * @return  一个后缀表达式
     */
    public static List<String> pareseSuffixExpressionList(List<String> strings) {
        //存放数字
        List<String> s1 = new ArrayList<>();
        //存放运算符
        Stack<String> stack = new Stack<>();

        for (String item : strings) {
            //判断是否是一个数字
            if (item.matches("\\d+")) {
                s1.add(item);
            } else if (item.equalsIgnoreCase("(")) {
                stack.push(item);
            } else if (item.equalsIgnoreCase(")")) {
                while (!stack.peek().equalsIgnoreCase("(")) {
                    //如果是“）”，则依次弹出stack栈顶的运算符，并压入s1，至到遇到“（”为止，此时将这一对括号丢掉
                    s1.add(stack.pop());
                }
                stack.pop();
            } else {
                //比较运算符的优先级
                while (s1.size() != 0 && !stack.empty() && Operation.getValue(stack.peek()) >= Operation.getValue(item)) {
                    s1.add(stack.pop());
                }
                stack.push(item);
            }
        }

        //把剩余的栈中内容全部弹出放入list中
        while (stack.size() != 0) {
            s1.add(stack.pop());
        }

        return s1;
    }


}
//比较运算符之间的优先级
class Operation {
    public final static int ADD = 1;
    public final static int SUB = 1;
    public final static int MUL = 2;
    public final static int DIV = 2;

    public static int getValue(String s) {
        int result = 0;
        switch (s) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "x":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("输入符号不存在！");
                break;
        }
        return result;
    }
}















